#include<stdio.h>
#include<iostream>
#include<queue>

using namespace std;

typedef struct BiTNode {
    int weight;
    struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;

BiTree CreatBiTree(int A[], int size) {
    if (size == 0) return nullptr;

    queue<BiTree> q;
    int index = 0;

    BiTree root = new BiTNode{ A[index++], nullptr, nullptr };
    q.push(root);

    while (!q.empty() && index < size) {
        BiTree current = q.front();
        q.pop();

        if (index < size) {
            if (A[index] != 0) {
                current->lchild = new BiTNode{ A[index], nullptr, nullptr };
                q.push(current->lchild);
            }
            index++;
        }

        if (index < size) {
            if (A[index] != 0) { 
                current->rchild = new BiTNode{ A[index], nullptr, nullptr };
                q.push(current->rchild);
            }
            index++;
        }
    }

    return root;
}

//递归（先序遍历）
int Function(BiTree& root, int deep) {
    if (!root) return 0;
    if (!root->lchild && !root->rchild)
        return root->weight * deep;
    return Function(root->lchild, deep + 1) + Function(root->rchild, deep + 1);
}

//层次遍历
#define QUEUE_MAX_SIZE 100
int CalcWPL(BiTree& root) {
    if (!root) return 0;
    BiTNode* Q[QUEUE_MAX_SIZE];
    int front = 0, rear = 0;
    int wpl = 0, level = 0;

    BiTNode* levelFin = root, * nextLevelFin = nullptr;
    //根节点入队
    Q[rear++] = root;

    while (front != rear) {
        BiTNode* p = Q[front++];
        if (!p->lchild && !p->rchild)
            wpl += p->weight * level;
        if (p->lchild) {
            Q[rear++] = p->lchild;
            nextLevelFin = p->lchild;
        }
        if (p->rchild) {
            Q[rear++] = p->rchild;
            nextLevelFin = p->rchild;
        }
        if (p == levelFin) {
            level++;
            levelFin = nextLevelFin;
        }
    }
    return wpl;
}


int main() {
    int A[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    BiTree T = CreatBiTree(A, 8);
    int ans = Function(T, 0);
    ans = CalcWPL(T);
    cout << ans << endl;
    return 0;
}